// https://www.lintcode.com/problem/coins-in-a-line/description

class Solution {
public:
    /**
     * @param n: An integer
     * @return: A boolean which equals to true if the first player will win
     */
    bool firstWillWin(int n) {
        vector<bool> res(n + 1);
        res[0] = false;
        res[1] = res[2] = true;
        for (int i = 3; i < n + 1; ++i)
        {
            res[i] = (res[i - 1] == false || res[i - 2] == false);
        }
        return res.back();
    }
    
    // 法二：
    // 可以证明, 当硬币数目是3的倍数的时候, 先手玩家必败, 否则他必胜：
    // 当硬币数目是3的倍数时, 每一轮先手者拿a个, 后手者拿3-a个即可, 后手必胜.
    // 若不是3的倍数, 先手者可以拿1或2个, 此时剩余硬币个数就变成了3的倍数.
    // bool firstWillWin(int n) {
    //     return n % 3;
    // }
};